Non-volatile memory devices such as Solid State Drives (SSDs) are finding new applications in consumer electronics. For example, they are replacing Hard Disk Drives (HDDs), which typically comprise rapidly rotating disks (platters). Non-volatile memories, sometimes referred to as ‘flash memories’ (for example, NAND and NOR flash devices), are used in media storage, cameras, mobile phones, mobile computers, laptop computers, USB flash drives, etc. Non-volatile memory provides a relatively reliable, compact, cost-effective, and easily accessible method of storing data when the power is off.
Non-volatile memory controllers, such as flash memory controllers, are used to manage the data stored in the non-volatile memory, and to act as an interface between a host and the non-volatile memory. A flash memory controller can include a Flash Translation Layer (FTL) that maps the host side logical addresses such as “logical block addresses” (LBAs) to the flash memory side “physical addresses” which correspond to physical locations. A mapping between the logical addresses and the physical addresses can change during operating of the system for various reasons including flash management.
During operation, a host system may request deletion of certain data stored on the non-volatile memory. Such deletion requests may result in invalidation commands from the host system to the non-volatile storage device for specific LBAs. These invalidation commands are intended to mark the data stored at these LBAs as invalid, or “Trim”. However, in practice, the data corresponding to that LBA may not be physically erased—the LBA, or a Bitmap table corresponding to the LBA, may be simply marked as invalid. If the data in the physical address corresponding to the invalid LBA or its Bitmap table is subsequently read, it can contain data previously present. Returning previously erased data can be undesirable, or may not meet specifications because it may pose a security threat in a number of situations.
A traditional Trim Bitmap typically resides in volatile memory, such as Dynamic Radom Accessible Memory (DRAM), and uses 1 bit per each LBA, with the Trim Bitmap size growing in direct proportion to the SSD capacity. When the Trim Bitmap size grows, it may not be possible to save the entire Trim Bitmap to non-volatile memory (e.g. NAND) during sudden power loss (SPL). As a result, it increases the difficulty for rebuilding process to maintain the accuracy of the Trim Bitmap after power loss. It also increases the processing overheads of Trim Bitmap journaling. Exemplary embodiments of the disclosure address these problems, both individually and collectively.